#include "Cataclysm/Geometry/geometry.h"
#include <vector>
#include <stdlib.h>
#include <sstream> // For Tripoint::string()

#define SGN(a) (((a)<0) ? -1 : 1)

std::vector<Point> line_to(int x0, int y0, int x1, int y1)
{
	int t = 0;
	std::vector<Point> ret;
	int dx = x1 - x0;
	int dy = y1 - y0;
	int ax = abs(dx) << 1;
	int ay = abs(dy) << 1;
	int sx = SGN(dx);
	int sy = SGN(dy);
	if (dy == 0) sy = 0;
	if (dx == 0) sx = 0;
	Point cur;
	cur.x = x0;
	cur.y = y0;

	int xmin = (x0 < x1 ? x0 : x1), ymin = (y0 < y1 ? y0 : y1),
			xmax = (x0 > x1 ? x0 : x1), ymax = (y0 > y1 ? y0 : y1);

	xmin -= abs(dx);
	ymin -= abs(dy);
	xmax += abs(dx);
	ymax += abs(dy);

	if (ax == ay)
	{
		do
		{
			cur.y += sy;
			cur.x += sx;
			ret.push_back(cur);
		} while ((cur.x != x1 || cur.y != y1) &&
				 (cur.x >= xmin && cur.x <= xmax && cur.y >= ymin && cur.y <= ymax));
	}
	else if (ax > ay)
	{
		do
		{
			if (t > 0)
			{
				cur.y += sy;
				t -= ax;
			}
			cur.x += sx;
			t += ay;
			ret.push_back(cur);
		} while ((cur.x != x1 || cur.y != y1) &&
				 (cur.x >= xmin && cur.x <= xmax && cur.y >= ymin && cur.y <= ymax));
	}
	else
	{
		do
		{
			if (t > 0)
			{
				cur.x += sx;
				t -= ay;
			}
			cur.y += sy;
			t += ax;
			ret.push_back(cur);
		} while ((cur.x != x1 || cur.y != y1) &&
				 (cur.x >= xmin && cur.x <= xmax && cur.y >= ymin && cur.y <= ymax));
	}
	return ret;
}

std::vector<Point> line_to(Point origin, Point target)
{
	return line_to(origin.x, origin.y, target.x, target.y);
}

std::vector<Tripoint> line_to(Tripoint origin, Tripoint target)
{
	return line_to(origin.x, origin.y, origin.z, target.x, target.y, target.z);
}

std::vector<Tripoint> line_to(int x0, int y0, int z0, int x1, int y1, int z1)
{
	int t = 0;
	std::vector<Tripoint> ret;
	int dx = x1 - x0;
	int dy = y1 - y0;
	int dz = z1 - z0;
	int ax = abs(dx) << 1;
	int ay = abs(dy) << 1;
	int sx = SGN(dx);
	int sy = SGN(dy);
	int dist = rl_dist(x0, y0, x1, y1);

	int z_step;
	if (dist == 0)
	{
		z_step = 0;
	}
	else
	{
		z_step = (100 * dz) / dist;
	}
	if (dy == 0) sy = 0;
	if (dx == 0) sx = 0;
	Tripoint cur;
	cur.x = x0;
	cur.y = y0;
	cur.z = z0;
	int z_value = 50; // Each tile is 100 microunits tall, start halfway up

	int xmin = (x0 < x1 ? x0 : x1), ymin = (y0 < y1 ? y0 : y1),
			xmax = (x0 > x1 ? x0 : x1), ymax = (y0 > y1 ? y0 : y1);

	xmin -= abs(dx);
	ymin -= abs(dy);
	xmax += abs(dx);
	ymax += abs(dy);

	if (ax == ay)
	{
		do
		{
			cur.y += sy;
			cur.x += sx;
			z_value += z_step;
			if (z_value < 0)
			{
				cur.z--;
				z_value += 100;
			}
			else if (z_value >= 100)
			{
				cur.z++;
				z_value -= 100;
			}
			ret.push_back(cur);
		} while ((cur.x != x1 || cur.y != y1) &&
				 (cur.x >= xmin && cur.x <= xmax && cur.y >= ymin && cur.y <= ymax));
	}
	else if (ax > ay)
	{
		do
		{
			if (t > 0)
			{
				cur.y += sy;
				t -= ax;
			}
			cur.x += sx;
			t += ay;
			z_value += z_step;
			if (z_value < 0)
			{
				cur.z--;
				z_value += 100;
			}
			else if (z_value >= 100)
			{
				cur.z++;
				z_value -= 100;
			}
			ret.push_back(cur);
		} while ((cur.x != x1 || cur.y != y1) &&
				 (cur.x >= xmin && cur.x <= xmax && cur.y >= ymin && cur.y <= ymax));
	}
	else
	{
		do
		{
			if (t > 0)
			{
				cur.x += sx;
				t -= ay;
			}
			cur.y += sy;
			t += ax;
			z_value += z_step;
			if (z_value < 0)
			{
				cur.z--;
				z_value += 100;
			}
			else if (z_value >= 100)
			{
				cur.z++;
				z_value -= 100;
			}
			ret.push_back(cur);
		} while ((cur.x != x1 || cur.y != y1) &&
				 (cur.x >= xmin && cur.x <= xmax && cur.y >= ymin && cur.y <= ymax));
	}
	return ret;
}

int rl_dist(int x0, int y0, int x1, int y1)
{
	int dx = (x0 > x1 ? x0 - x1 : x1 - x0), dy = (y0 > y1 ? y0 - y1 : y1 - y0);
	return (dx > dy ? dx : dy);
}

int rl_dist(Point origin, Point target)
{
	return rl_dist(origin.x, origin.y, target.x, target.y);
}

int rl_dist(int x0, int y0, int z0, int x1, int y1, int z1)
{
	int dx = (x0 > x1 ? x0 - x1 : x1 - x0), dy = (y0 > y1 ? y0 - y1 : y1 - y0),
			dz = (z0 > z1 ? z0 - z1 : z1 - z0);
	if (dx > dy && dx > dz)
	{
		return dx;
	}
	if (dy > dz)
	{
		return dy;
	}
	return dz;
}

std::string Point::str()
{
	std::stringstream ret;
	ret << "[" << x << ":" << y << "]";
	return ret.str();
}

std::string Tripoint::str()
{
	std::stringstream ret;
	ret << "[" << x << ":" << y << ":" << z << "]";
	return ret.str();
}

int rl_dist(Tripoint origin, Tripoint target)
{
	return rl_dist(origin.x, origin.y, origin.z, target.x, target.y, target.z);
}

int manhattan_dist(int x0, int y0, int x1, int y1)
{
	return abs(x1 - x0) + abs(y1 - y0);
}

int manhattan_dist(Point origin, Point target)
{
	return manhattan_dist(origin.x, origin.y, target.x, target.y);
}

int manhattan_dist(int x0, int y0, int z0, int x1, int y1, int z1)
{
	return abs(x1 - x0) + abs(y1 - y0) + abs(z1 - z0);
}

int manhattan_dist(Tripoint origin, Tripoint target)
{
	return manhattan_dist(origin.x, origin.y, origin.z,
			target.x, target.y, target.z);
}

bool is_adjacent_no_diag(int x0, int y0, int x1, int y1)
{
	return is_adjacent_no_diag(Point(x0, y0), Point(x1, y1));
}

bool is_adjacent_no_diag(Point A, Point B)
{
	return ((A.x == B.x && abs(A.y - B.y) <= 1) ||
			(A.y == B.y && abs(A.x - B.x) <= 1));
}

bool is_adjacent_diag(int x0, int y0, int x1, int y1)
{
	return is_adjacent_diag(Point(x0, y0), Point(x1, y1));
}

bool is_adjacent_diag(Point A, Point B)
{
	return (abs(A.x - B.x) <= 1 && abs(A.y - B.y) <= 1);
}

Direction_full get_general_direction(Point origin, Point target)
{
	int dx = target.x - origin.x;
	int dy = target.y - origin.y;
	int ax = abs(dx), ay = abs(dy);

	if (dx == 0)
	{
		if (dy == 0)
		{
			return DIRFULL_NULL;
		}
		else if (dy > 0)
		{
			return DIRFULL_SOUTH;
		}
		else
		{
			return DIRFULL_NORTH;
		}
	}
	else if (dx > 0)
	{
		if (dy >= 0)
		{
			if (ay / 2 >= ax)
			{
				return DIRFULL_SOUTH;
			}
			else if (ax / 2 >= ay)
			{
				return DIRFULL_EAST;
			}
			else
			{
				return DIRFULL_SOUTHEAST;
			}
		}
		else
		{
			if (ay / 2 > ax)
			{
				return DIRFULL_NORTH;
			}
			else if (ax / 2 >= ay)
			{
				return DIRFULL_EAST;
			}
			else
			{
				return DIRFULL_NORTHEAST;
			}
		}
	}
	else
	{
		if (dy >= 0)
		{
			if (ay / 2 >= ax)
			{
				return DIRFULL_SOUTH;
			}
			else if (ax / 2 >= ay)
			{
				return DIRFULL_WEST;
			}
			else
			{
				return DIRFULL_SOUTHWEST;
			}
		}
		else
		{
			if (ay / 2 > ax)
			{
				return DIRFULL_NORTH;
			}
			else if (ax / 2 >= ay)
			{
				return DIRFULL_WEST;
			}
			else
			{
				return DIRFULL_NORTHWEST;
			}
		}
	}
	return DIRFULL_NULL;
}

Direction_full get_general_direction(Tripoint origin, Point target)
{
	return get_general_direction(Point(origin.x, origin.y), target);
}

Direction_full get_general_direction(Point origin, Tripoint target)
{
	return get_general_direction(origin, Point(target.x, target.y));
}

Direction_full get_general_direction(Tripoint origin, Tripoint target)
{
	return get_general_direction(Point(origin.x, origin.y),
			Point(target.x, target.y));
}

std::string Direction_name(Direction dir)
{
	switch (dir)
	{
	case DIR_NULL:
		return "None";
	case DIR_NORTH:
		return "North";
	case DIR_EAST:
		return "East";
	case DIR_SOUTH:
		return "South";
	case DIR_WEST:
		return "West";
	}
	return "???";
}

std::string Direction_name(Direction_full dir)
{
	switch (dir)
	{
	case DIRFULL_NULL:
		return "None";
	case DIRFULL_NORTH:
		return "North";
	case DIRFULL_NORTHEAST:
		return "Northeast";
	case DIRFULL_EAST:
		return "East";
	case DIRFULL_SOUTHEAST:
		return "Southeast";
	case DIRFULL_SOUTH:
		return "South";
	case DIRFULL_SOUTHWEST:
		return "Southwest";
	case DIRFULL_WEST:
		return "West";
	case DIRFULL_NORTHWEST:
		return "Northwest";
	}
	return "???";
}
